package com.shm.leetcode;

/**
 * 778. 水位上升的泳池中游泳
 * 在一个 N x N 的坐标方格 grid 中，每一个方格的值 grid[i][j] 表示在位置 (i,j) 的平台高度。
 *
 * 现在开始下雨了。当时间为 t 时，此时雨水导致水池中任意位置的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。
 *
 * 你从坐标方格的左上平台 (0，0) 出发。最少耗时多久你才能到达坐标方格的右下平台 (N-1, N-1)？
 *
 *
 *
 * 示例 1:
 *
 * 输入: [[0,2],[1,3]]
 * 输出: 3
 * 解释:
 * 时间为0时，你位于坐标方格的位置为 (0, 0)。
 * 此时你不能游向任意方向，因为四个相邻方向平台的高度都大于当前时间为 0 时的水位。
 *
 * 等时间到达 3 时，你才可以游向平台 (1, 1). 因为此时的水位是 3，坐标方格中的平台没有比水位 3 更高的，所以你可以游向坐标方格中的任意位置
 * 示例2:
 *
 * 输入: [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
 * 输出: 16
 * 解释:
 *  0  1  2  3  4
 * 24 23 22 21  5
 * 12 13 14 15 16
 * 11 17 18 19 20
 * 10  9  8  7  6
 *
 * 最终的路线用加粗进行了标记。
 * 我们必须等到时间为 16，此时才能保证平台 (0, 0) 和 (4, 4) 是连通的
 *
 *
 * 提示:
 *
 * 2 <= N <= 50.
 * grid[i][j] 是 [0, ..., N*N - 1] 的排列。
 * @author SHM
 */
public class SwimInWater {
    int N;
    int[][] dirs ={{1,0},{-1,0},{0,1},{0,-1}};

    /**
     * 由于题目要我们找的是最少等待时间，可以模拟下雨的过程，把网格抽象成一个无权图，每经过一个时刻，就考虑此时和雨水高度相等的单元格，考虑这个单元格的上、下、左、右、四个方向，并且高度更低的单元格，把它们在并查集中进行合并
     *
     * 复杂度分析
     *
     * 时间复杂度：O(N^2 \log N)O(N
     * 2
     *  logN)，其中 NN 是方格的边长，计数排序 O(N^2)O(N
     * 2
     *  )，合并四周、检查起点和终点是否同属于一个连通分量 O(\log N^2)O(logN
     * 2
     *  )，总的时间复杂度为 O(N^2 + N^2\log N^2) = O(N^2 + 2N^2 \log N) = O(N^2 \log N)O(N
     * 2
     *  +N
     * 2
     *  logN
     * 2
     *  )=O(N
     * 2
     *  +2N
     * 2
     *  logN)=O(N
     * 2
     *  logN)；
     * 空间复杂度：O(N^2)O(N
     * 2
     *  )，数组 index 的长度，并查集底层的长度均为 N^2N
     * 2
     *  。
     *
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/swim-in-rising-water/solution/shui-wei-shang-sheng-de-yong-chi-zhong-y-862o/
     * @param grid
     * @return
     */
    public int swimInWater(int[][] grid) {
        this.N = grid.length;

        int len = N*N;

        int[] index = new int[len];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                index[grid[i][j]] = getIndex(i,j);
            }
        }

        UnionFind uf = new UnionFind(len);
        //按平台高度升序遍历
        for (int i = 0; i < len; i++) {
            int x = index[i]/N;
            int y = index[i]%N;

            for (int[] dir : dirs) {
                int newX = x + dir[0];
                int newY = y + dir[1];

                if(inArea(newX,newY)&&grid[newX][newY]<=i){
                    uf.union(index[i],getIndex(newX,newY));
                }
                if(uf.find(0)==uf.find(len-1)){
                    return i;
                }
            }
        }
        return -1;
    }

    int getIndex(int x,int y){
        return x*N+y;
    }

    boolean inArea(int x,int y){
        return x>=0&&x<N&&y>=0&&y<N;
    }


    class UnionFind{
        int[] parent;
        int count;
        UnionFind(int n){
            parent = new int[n];
            count = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        int find(int x){
            if(parent[x]!=x){
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        void union(int x, int y){
            int newX = find(x);
            int newY = find(y);
            if(newX==newY){
                return;
            }
            parent[newY] = newX;
            count--;
        }

        int getCount(){
            return count;
        }
    }
}
